import java.util.LinkedList;
import java.util.Queue;

/*
*
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class NumIslands {

//    Queue<int[]> together = new LinkedList<>();
//    Queue<int[]> noVisited = new LinkedList<>();
//
//    public int numIslands(char[][] grid) {
//        int row = grid.length;
//        if(row <= 0){
//            return 0;
//        }
//        int col = grid[0].length;
//        if(col <= 0){
//            return 0;
//        }
//        noVisited.add(new int[]{0,0});
//        int count = 0;
//        while(!noVisited.isEmpty()){
//            int[] pos = noVisited.poll();
//            if(isIsland(grid, pos[0], pos[1], row, col)){
//                count ++;
//            }
//        }
//        return count;
//    }
//
//    boolean isIsland(char[][] grid, int i, int j, int row, int col){
//
//        int val = grid[i][j];
//        boolean island = false;
//        if('1' == val){
//            island = true;
//        }
//        //set to visited
//        grid[i][j] = 'v';
//        addNeighbor(i, j, row, col);
//        while(!together.isEmpty()){
//            int[] pos = together.poll();
//            int x = pos[0];
//            int y = pos[1];
//            int v = grid[x][y];
//            if(v == 'v'){
//                continue;
//            }
//            if(v != val){
//                noVisited.add(pos);
//            } else {
//                grid[x][y] = 'v';
//                addNeighbor(x, y, row, col);
//            }
//
//        }
//
//        return island;
//    }
//
//    private void addNeighbor(int i, int j, int row, int col){
//        if(i + 1 < row){
//            together.add(new int[]{i + 1, j});
//        }
//        if(i - 1 >= 0){
//            together.add(new int[]{i - 1, j});
//        }
//        if(j + 1 < col){
//            together.add(new int[]{i, j + 1});
//        }
//        if(j - 1 >= 0){
//            together.add(new int[]{i, j - 1});
//        }
//    }

    int[][] neighbor = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    public int numIslands(char[][] grid) {
        int row = grid.length;
        if (row <= 0 || grid[0].length <= 0) {
            return 0;
        }
        int col = grid[0].length;
        int count = 0;
        for(int i=0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == '1'){
                    dfs(i, j, grid, row, col);
                    count ++;
                }
            }
        }
        return count;
    }

    private void dfs(int i, int j, char[][] grid, int row, int col){
        if(grid[i][j] == '1') {
            grid[i][j] = '0';
            for (int m = 0; m < 4; m++) {
                int x = neighbor[m][0] + i;
                int y = neighbor[m][1] + j;
                if (x >= 0 && x < row && y >= 0 && y < col) {
                    dfs(x, y, grid, row, col);
                }
            }
        }
    }


}
